package org.example.dataStructure.linkedList;

import org.example.dataStructure.queue.MyQueue;

public class MyLinkedList<T>{

    private Node<T> head;
    private Node<T> tail;

    private static class Node<T>{
        public Node<T> latter;//后一个元素
        public T value;//存入的数据
        public Node<T> previous;//前一个元素
    }

    //向链表新增元素
    public void add(T value){
        if(this.head == null){
            Node<T> tNode = new Node<>();
            tNode.value = value;
            tNode.previous = tNode;
            tNode.latter = tNode;
            this.head = tNode;
            this.tail = tNode;
        }else if(this.head == this.tail){
            Node<T> tNode = new Node<>();
            tNode.value = value;
            //将tNode的前一个元素指向头部元素
            tNode.previous = this.head;
            //将tNode的后一个元素指向头部元素
            tNode.latter = this.head;
            //将头部元素的后一个指向指向tNode
            this.head.latter = tNode;
            //将头部元素的前一个指向指向tNode
            this.head.previous = tNode;
            this.tail = tNode;
        }else{
            Node<T> tNode = new Node<>();
            tNode.value = value;
            //改变末尾元素的指向
            this.tail.latter = tNode;
            //改变tNode前一个的指向
            tNode.previous = this.tail;
            //改变tNode后一个的指向
            tNode.latter = this.head;
            //改变头部元素的前一个指向
            this.head.previous = tNode;
            //将tNode变为最后一个元素
            this.tail = tNode;
        }
    }

    //获取总元素个数
    public Integer size(){
        int index = 0;
        if(this.head == null){
            return index;
        }else{
            Node<T> node = this.head;
            do {
                index ++;
                node = node.latter;
            }while (node != this.head);
        }
        return index;
    }

    //将元素插入到链表中
    public void insert(Integer position,T value){
        //链表中没有元素，立即返回
        if(this.head == null){
            return;
        }
        //在链表中查询插入位置
        Node<T> node = this.head;
        int copyPosition = position;
        while (position>0){
            if(node == this.head && position<copyPosition){
                return;
            }else {
                node = node.latter;
                if(node == this.head && position<copyPosition){
                    return;
                }
            }
            position --;
        }
        //插入元素
        Node<T> tNode = new Node<>();
        tNode.value = value;
        tNode.latter = node.latter;
        if(tNode.latter == this.head){
            this.tail = tNode;
        }
        node.latter = tNode;
        tNode.previous = node;
    }

    public String toString(){
        if(this.head == null){
            return null;
        }

        StringBuilder builder = new StringBuilder();
        builder.append("[");
        Node<T> node = this.head;
        do {
            builder.append(node.value);
            builder.append(",");
            node = node.latter;
        }while (node != this.head);
        builder.deleteCharAt(builder.length()-1);
        builder.append("]");
        return builder.toString();
    }

    public void delete(Integer position){
        //链表中没有元素，立即返回
        if(this.head == null){
            return;
        }
        //在链表中需要删除的元素
        Node<T> node = this.head;
        int copyPosition = position;
        while (position>0){
            if(node == this.head && position<copyPosition){
                return;
            }else {
                node = node.latter;
                if(node == this.head && position<copyPosition){
                    return;
                }
            }
            position --;
        }

        if(node == this.head && this.head == this.tail){
            this.head = null;
            this.tail = null;
        }else{
            Node<T> previous = node.previous;
            Node<T> latter = node.latter;

            latter.previous = previous;
            previous.latter = latter;
            this.head = latter;
        }
    }

}
